package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/4 11:50
 * @description：https://leetcode-cn.com/problems/cat-and-mouse/
 */
public class 猫和老鼠 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        static final int MOUSE_WIN = 1;
        static final int CAT_WIN = 2;
        static final int DRAW = 0;
        int n;
        int[][] graph;
        int[][][] dp;

        public int catMouseGame(int[][] graph) {
            this.n = graph.length;
            this.graph = graph;
            this.dp = new int[n][n][n * 2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    Arrays.fill(dp[i][j], -1);
                }
            }
            return getResult(1, 2, 0);
        }

        public int getResult(int mouse, int cat, int turns) {
            if (turns == n * 2) {
                return DRAW;
            }
            if (dp[mouse][cat][turns] < 0) {
                if (mouse == 0) {
                    dp[mouse][cat][turns] = MOUSE_WIN;
                } else if (cat == mouse) {
                    dp[mouse][cat][turns] = CAT_WIN;
                } else {
                    getNextResult(mouse, cat, turns);
                }
            }
            return dp[mouse][cat][turns];
        }

        public void getNextResult(int mouse, int cat, int turns) {
            int curMove = turns % 2 == 0 ? mouse : cat;
            int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
            int result = defaultResult;
            int[] nextNodes = graph[curMove];
            for (int next : nextNodes) {
                if (curMove == cat && next == 0) {
                    continue;
                }
                int nextMouse = curMove == mouse ? next : mouse;
                int nextCat = curMove == cat ? next : cat;
                int nextResult = getResult(nextMouse, nextCat, turns + 1);
                if (nextResult != defaultResult) {
                    result = nextResult;
                    if (result != DRAW) {
                        break;
                    }
                }
            }
            dp[mouse][cat][turns] = result;
        }
    }
}
